| |
| description |
Relational division, also known as small divide, is a derived
operator of the relational algebra that realizes a many-to-one set
containment test, where a set is represented as a group of tuples:
Small divide discovers which sets in a dividend relation contain all
elements of the set stored in a divisor relation. The great divide
operator extends small divide by realizing many-to-many set
containment tests. It is also similar to the set containment join
operator for schemas that are not in first normal form.
Neither small nor great divide has been implemented in commercial
relational database systems although the operators solve important
problems and many efficient algorithms for them exist. We present
algebraic laws that allow rewriting expressions containing small or
great divide, illustrate their importance for query optimization,
and discuss the use of great divide for frequent itemset discovery,
an important data mining primitive.
A recent theoretic result shows that small divide must be
implemented by special purpose algorithms and not be simulated by
pure relational algebra expressions to achieve efficiency.
Consequently, an efficient implementation requires that the
optimizer treats small divide as a first-class operator and
possesses powerful algebraic laws for query rewriting.
|
| publisher |
IEEE Computer Society
|
| type |
Text
|
| Article in Proceedings
|
| source |
In: Liu, Ling (ed.); Reuter, Andreas (ed.); Whang, Kyu-Young (ed.);
Zhang, Jianjun (ed.): Proceedings of the 22nd International
Conference on Data Engineering, ICDE 2006, pp. 21-21
|
| ftp://ftp.informatik.uni-stuttgart.de/pub/library/ncstrl.ustuttgart_fi/INPROC-2006-32/INPROC-2006-32.pdf
|
| contributor |
IPVS, Anwendersoftware
|
| format |
application/pdf
|
| 233689 Bytes
|
| subject |
Mathematical Logic (CR F.4.1)
|
| Database Management Languages (CR H.2.3)
|